﻿#ifndef __RADIXSORT__
#define __RADIXSORT__
#include "SortTool.h"
#include "insertion.h"
//MSD stands for Most significant digit(最高位优先)
//LSD stands for Least significant digit(最低位优先)
#define MSD 1 //0 为LSD
#define R 2 //基数
#define SMALL 16 //定义小的划分量，大牛的说法是：一般在10~25之间可以达到改善的效果
#if MSD
//1.值得注意的是，如果是循环实现算法，则在表示偏移量的位置可以不用加上left
//如果是采用递归的形式实现，则必须在偏移量的位置加上left
//2.这里的基数排序，R取值为2.虽然采用的是计数排序的形式
//但排序的过程与快速排序一样，对每一位进行01的划分，进而递归到下一位
//3.getbit() 应该看做是一个抽象方法，他用来提取待排序数项的“位”，本算法实现是提取数字的二进制的位
//从算法实现角度来看，第三点最重要；而前两者是我在实现过程中体会最深的两点
template <class item>
void radixsort_binary(item arr[], int left, int right, int digit){
	if(  arr == NULL ||digit >= 32 || left >= right ) return;
	
	//为了提高算法的执行效,对小的划分进行插入排序
	if(right - left <=SMALL) { insertion(arr, left, right); return;} 
	
	int count[R],bin[R];
	static int aux[MAX_ARRAY_NUM];
	for(int i = 0; i < R; ++i) count[i] = 0;
	for(int i = left; i <= right; ++i)	++count[getbit(arr[i],digit)];
	for(int i = 1; i < R; ++i) count[i] += count[i-1];
	for(int i = 0; i < R; ++i) bin[i] = count[i];
	for(int i = right; i >= left; --i) aux[left+(--count[getbit(arr[i],digit)])] = arr[i];//倒序回放，才能保证正序结果
	for(int i = left; i <= right; ++i) arr[i] = aux[i];

	radixsort_binary(arr, left,  left + bin[0]-1, digit+1);
	for(int i = 0; i < R-1; ++i)
		radixsort_binary(arr, left + bin[i], left + bin[i+1]-1, digit+1);
}

template <class item>
void radixsort(item arr[], int left, int right){
	radixsort_binary(arr, left, right, 0);
}
#else
//事实上只有排序的方法稳定时，LSD才能奏效
//换句话说，二进制的快速排序方法在这里是无法演的，而计数排序则可以继续
//大牛说：LSD 对32位随机整数进行排序，R取16位的字节，则可以比快速排序还要快
template <class item>
void radixsort(item arr[], int left, int right){
	if(arr == NULL || left >= right ) return;
	int count[R], aux[MAX_ARRAY_NUM];
	for(int i = BITSWORD-1; i >= 0 ; --i){
		for(int j = 0 ; j < R; ++j) count[j] = 0;
		for(int j = left; j <= right; ++j) ++count[getbit(arr[j],i)];
		for(int j = 1; j < R; ++j) count[j] += count[j-1];
		for(int j = right; j >= left; --j) aux[--count[getbit(arr[j],i)]] = arr[j];
		for(int j = left; j <= right; ++j) arr[j] = aux[j];
	}
}
#endif
#endif